package com.github.hgkmail.hello.leetcode101.pointer.graph.bipartite;

import com.github.hgkmail.hello.leetcode101.base.CommonUtil;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.List;
import java.util.Queue;

public class LC785IsGraphBipartite {
    public boolean dfs(int[][] graph, int[] color, int vertex) {
        //邻接点列表
        int[] adjVertexes = graph[vertex];

        for (int i = 0; i < adjVertexes.length; i++) {
            int adj=adjVertexes[i];
            if (color[adj]!=0) {
                if (color[adj]==color[vertex]) { //相连又相同颜色，违背二分图定义
                    return false;
                }
            } else {
                color[adj] = -color[vertex]; //相连的点要在不同的集合，因此染成不同的颜色
                if (!dfs(graph, color, adj)) {
                    return false;
                }
            }
        }
        return true;
    }

    //染色法1，使用dfs，不太推荐
    public boolean isBipartite(int[][] graph) {
        int len= graph.length;
        if (len<=0) {
            //空图算二分图
            return true;
        }
        //0:未染色 1:白色 -1:黑色
        int[] color=new int[len];
        Arrays.fill(color, 0);

        //这里必须遍历所有的点，因为可能有多个连通分量
        for (int i = 0; i < len; i++) {
            if(color[i]==0) {
                color[i]=1;
                if(!dfs(graph, color, i)) {
                    return false;
                }
            }
        }

        return true;
    }

    //染色法2，使用bfs，推荐
    //bfs非常适合染色法
    public boolean isBipartite2(int[][] graph) {
        int len= graph.length;
        if (len<=0) {
            //空图算二分图
            return true;
        }
        //0:未染色 1:白色 -1:黑色
        int[] color=new int[len];
        Arrays.fill(color, 0);

        Queue<Integer> queue=new ArrayDeque(len);
        int v, u;
        int[] adjVertexes;
        for (int i = 0; i < len; i++) {
            if (color[i]==0) { //如果未染色，随便染个颜色
                color[i]=1;
                queue.offer(i);
            }
            while (!queue.isEmpty()) {
                v=queue.poll();
                adjVertexes = graph[v];
                for (int j = 0; j < adjVertexes.length; j++) {
                    u=adjVertexes[j];
                    if (color[u]==0) {
                        color[u] = -color[v];
                        queue.offer(u);
                    } else if(color[u]==color[v]) {
                        return false;
                    }
                }
            }//while
        }//fir

        return true;
    }

    public static void main(String[] args) {
        List<List<Integer>> graph=CommonUtil.createGraphByAdj("[[3,4,6],[3,6],[3,6],[0,1,2,5],[0,7,8],[3],[0,1,2,7],[4,6],[4],[]]");
        CommonUtil.printEdge(graph);
        int[][] lcGraph = CommonUtil.getLcGraph(graph);
        boolean res = new LC785IsGraphBipartite().isBipartite2(lcGraph);
        System.out.println(res);
    }
}
